package 第六周;

/*
 * @author  YxinMiracle
 * @date  2022-05-05 12:15
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 零钱兑换 {

    public int coinChange(int[] coins, int amount) {
        int[] opt = new int[amount+1];
        opt[0] = 0;
        for (int i = 1; i <= amount; i++) {
            opt[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >=0){
                    opt[i] = Math.min(opt[i],opt[i-coins[j]]+1);
                }
            }
        }
        return opt[amount] == Integer.MAX_VALUE ? -1 : opt[amount];
    }

}
